The present invention relates to the art of generating alphanumeric characters or other symbols for reproduction by a cathode ray tube (CRT), a laser beam scanner or other flying spot character imaging device which is capable of being electronically controlled. More particularly, the present invention concerns a font storage system for use in a character generator whereby a font of characters or other symbols are stored in a digital code.
The field of automated typesetting has experienced ever-accelerating advances since Ottmar Mergenthaler developed the Linotype.RTM. machine for semi-automatically producing lines of type. The Linotype machine and its progeny of "hot metal" typesetters have been called the first generation of automatic typesetters. These typesetters were refined over the years and are still in use in some locations.
The second generation of typesetters, which were pioneered by Rene Higonnet and Louis Moyroud, among others, are called photo-mechanical typesetters, or simply phototypesetters. In these machines, one or more fonts of characters are arranged on a photographic negative. Selected characters are automatically projected through an optical system and positioned in a line on photographic film. Not only are these phototypesetters now less expensive than their first generation parents, but refinements in the machines led to faster speed, better quality and greater typographic flexibility. Phototypesetters are currently enjoying a period of maximum use in the graphic arts industry, but are being improved upon by third generation machines: the so-called CRT (and laser) typesetters.
In CRT typesetters characters are electronically generated and written onto photographic film, thus eliminating most of the mechanical movements characteristic of second generation phototypesetters. This change from mechanics to electronics is resulting in still faster speed and greater typographic flexibility, as well as less frequent adjustments and fewer changes in "font dressings" or stored fonts which are necessary on all second generation typesetters. The CRT typesetters are, as a rule, more expensive than their second generation counterparts so that, while they have become the dominant machines in the newspaper market, they are only just beginning to gain significance in non-newspaper applications. It is expected, however, that the price of CRT typesetters will come down as volume increases and new machines are developed to take advantage of advances in electronic circuit technology.
There are generally two methods by which character fonts are stored in third generation typesetters. The so-called "analog" machines store the character masters on photographic film grids. These masters are scanned with a flying spot scanner at the same time that the character is imaged in the appropriate size on the output CRT. A second class of machines, the so-called "digital" machines, rely on character masters which have been coded in digital form and stored on some kind of digital storage medium in the machine. With such digital machines the ability to store a large font library within the typesetter is limited only by the cost of providing a storage medium of suitable size so that it is not normally necessary for the user to repeatedly "dress" the machine by inserting new fonts. In addition, the digital machines are at least twice as fast as the fastest analog (photographic store) machines and are capable of imaging cleaner, more uniform characters than the analog machines.
Originally, when digital CRT typesetters were first introduced, the principal concern in preparing digital font masters was simply data reduction. In order to reproduce characters which were indistinguishable from characters imaged from photographic masters or printed by cast type faces, it is necessary to encode each character with a relatively fine grid; i.e., a "matrix" with a high resolution or density of raster elements. At a minimum, and for small characters, the grid may comprise 70 columns and 100 rows or 7,000 raster elements. If the presence or absence of a portion of a character in each raster element is represented by one bit, 7,000 bits of information are required to represent all elements of the grid. The U.S. Pat. No. 3,305,841 to Schwartz discloses a CRT typesetter in which the number of bits required to represent a character is compressed at least by a factor of 3 in every case, and by a factor of 5 or more in an average case. This data reduction is accomplished by identifying with a digital code the starting and ending points of the line segments (dark portions) of a character in each row or column of the grid. Thus, in a grid comprising 7,000 raster elements, the data required to define a character was reduced from 7,000 bits to approximately 1,500.
The U.S. Pat. No. 3,471,848 to Manber discloses an improvement on the above-noted system which permits an additional reduction in data. With this system, the starting and ending points of a line segment within a row or column of the grid are encoded as an incremental increase or decrease from the starting and ending points, respectively, on a line segment in the previous row or column. Data compression is achieved because the numbers required to define the incremental addresses of a line segment are smaller than the numbers required to define the absolute addresses.
The U.S. Pat. Nos. 3,305,841 and 3,471,848 also disclose a number of other techniques of data compression with digitally encoded characters:
(1) The provision of a code which indicates the number of blank rows or columns on one side or the other (or both sides) of the character.
(2) The provision of a "line repeat" code which indicates that the line segment or segments in a row or column are at the same position(s) as the segment(s) of the previous row or column.
(3) The provision of a code indicating that a selected start or end of a line segment address is to be repeated a prescribed number of times.
Notwithstanding the various techniques of data reduction, digital font masters produced in accordance with the teaching of the U.S. Pat. Nos. 3,305,841 and 3,471,848 are appreciably more expensive than the photographic masters used in the analog CRT typesetters. There are two fundamental reasons for this:
(1) The digital machines size type by varying the spacing of strokes on the output tube. There are practical limits as to how far up and down an image can be sized in this fashion. Therefore, these machines have required several different master fonts in order to cover a complete range of output sizes.
(2) Digitizing type fonts is a tedious, time consuming process. Character masters are first prepared on a standard grid and then scanned automatically to determine which raster points on the grid fall within the character. The resulting dot matrix is then "digitized" in accordance with a particular code and stored in a machine readable form.
The U.S. Pat. No. 4,029,947 to Evans et al. discloses a character encoding and decoding scheme for a CRT typesetter which makes it possible to eliminate the first disadvantage noted above. This is accomplished by encoding the normalized character outline (as distinguished from size-related character row or column line segments) with a series of successive slopes and curvatures from an initial starting point or points for the character. For this purpose, a large number of slopes and curvatures are available for selection by the encoder, with each of such slopes and curvatures being identified by its individual binary code number.
Another character representation scheme which treats characters in terms of normalized character outlines was used by the Model 1601 CRT typesetter manufactured by SEACO Computer Display in Garland, Texas. This machine, which is disclosed in the Seybold Report, Vol. 1, Nos. 12 and 13 (Feb. 14 and 28, 1972), stored the absolute coordinates of a number of points on the character outline. Data reduction was achieved because intermediate points on the outline between stored points were considered to follow straight lines between the stored points.
The SEACO 1601 CRT typesetter, as well as the typesetter disclosed in the U.S. Pat. No. 4,029,947, determine the data required for imaging the character over a range of point sizes from a single set of encoded character outline data by means of a calculation procedure, carried out either by software or hardware. In contrast, the CRT typesetters disclosed in the U.S. Pat. Nos. 3,305,841 and 3,471,848 perform a minimum of calculation because the information required to "stroke" successive line segments (i.e., the start and end addresses of each line segment) are present in the data.
Thus, while various digital character encoding schemes have been defined in the art for CRT typesetters, no scheme has been devised which optimally meets all the various requirements. These are:
(1) The encoding scheme should be conservative of space in digital memory.
(2) A single set of data defining a character should be usable to generate character images in all point sizes.
(3) The encoded data should be capable of being converted into the form required to control the CRT by a relatively simple and easy-to-automate computation procedure.
(4) The character encoding scheme should be defined by rules which are easily automated, so that the coded data may be generated from photomasters, red dot matrices or from some other code by a digital computer.